package com.mdnote.practice.dfs_bfs;


import sun.util.PreHashedMap;

import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.concurrent.LinkedBlockingDeque;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/9/17
 * @description 单词接龙
 */
public class LeetCode127 {
    public static void main(String[] args) {
        LeetCode127 leetCode127 = new LeetCode127();
        int step = leetCode127.ladderLength("kiss", "tusk", Arrays.asList("miss","dusk","kiss","musk","tusk","diss","disk","sang","ties","muss"));

        System.out.println(step);
    }
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {

        if (!wordList.contains(endWord)) {
            return 0;
        }

        // 广度优先算法
//        int step = bfs(beginWord, endWord, wordList);
        // 双向广度优先算法
        int step = dDfs(beginWord, endWord, wordList);
        return step;
    }

    private int dDfs(String beginWord, String endWord, List<String> wordList) {

        // 先把模板写下来
        HashSet<String> beginVisitedSet = new HashSet<>();
        beginVisitedSet.add(beginWord);

        HashSet<String> endVisitedSet = new HashSet<>();
        endVisitedSet.add(endWord);

        HashSet<String> wordSet = new HashSet<>(wordList);

        HashSet<String> visited = new HashSet<>();
        int step = 1;

        while (!beginVisitedSet.isEmpty() && !endVisitedSet.isEmpty()) {

            // 让beginQueue指向小的队列
            if (beginVisitedSet.size() > endVisitedSet.size()) {
                HashSet<String> temp = beginVisitedSet;
                beginVisitedSet = endVisitedSet;
                endVisitedSet = temp;
            }

            // 记录下一层遍历的元素
            HashSet<String> nextLevel = new HashSet<>();
            // 判断当前层的元素(begin指向)是否合法，合法就add到next中
            for (String current : beginVisitedSet) {
                char[] chars = current.toCharArray();
                char[] originChar = Arrays.copyOf(chars, chars.length);
                for (int i = 0; i < chars.length; i++) {
                    for (char j = 'a'; j <= 'z'; j++) {

                        chars[i] = j;
                        String newString = new String(chars);
                        if (endVisitedSet.contains(newString) )  {
                            return step + 1;
                        }
                        if (wordSet.contains(newString) && !visited.contains(newString)) {
                            // 避免成环
                            nextLevel.add(newString);
                            visited.add(newString);
                        }

                    }
                    chars[i] = originChar[i];
                }
            }
            beginVisitedSet = nextLevel;
            step ++;
        }
        return 0;
    }

    private int bfs(String beginWord, String endWord, List<String> wordList) {

        // 先把模板写下来
        LinkedList<String> queue = new LinkedList<>();
        queue.add(beginWord);

        // 用于记录访问记录的哈希表
        HashSet<String> visitedSet = new HashSet<>();
        visitedSet.add(beginWord);

        // 单词列表
        HashSet<String> wordSet = new HashSet<>(wordList);
        int step = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String tempString = queue.removeFirst();
                // 把当前的字符串转换为字符数组
                char[] chars = tempString.toCharArray();
                // 保存一下先
                char[] oldChars = Arrays.copyOf(chars, chars.length);

                for (int j = 0; j < chars.length; j++) {
                    //  对当前字母进进行更换
                    for (char k = 'a'; k <= 'z'; k++) {
                        chars[j] = k;
                        // 判断一下变换后在不在单词列表里
                        String newString = new String(chars);
                        // 如果已经是目标单词了
                        if (endWord.equals(newString)) {
                            return step + 1;
                        }
                        // 不是目标单词，判断他是不是合法的
                        if (wordSet.contains(newString) && !visitedSet.contains(newString)) {
                            queue.addLast(newString);
                            visitedSet.add(newString);
                        }
                    }
                    chars[j] = oldChars[j];
                }
                // current logic
            }
            step ++;
        }
        return 0;
    }


}
